package com.leetcode;

import static org.testng.Assert.assertEquals;
import org.testng.annotations.Test;

public class PalindromePartition2 {
	public int minCut(String s) {
		int N = s.length();
		boolean[][] isP = new boolean[N][N];
		for (int i=0; i<N; i++) isP[i][0] = true;
		for (int len=1; len<N; len++) {
			for (int i=0; i<N-len; i++) {
				if (s.charAt(i+len) == s.charAt(i) &&
					(len<2 || isP[i+1][len-2])) {
					isP[i][len] = true;
				}
			}
		}
		
		int[] minCut = new int[N];
		for (int end=1; end<N; end++) {
			if (isP[0][end]) {
				minCut[end] = 0;
				continue;
			}
			minCut[end] = end;
			for (int first=end; first>0; first--) {
				if (isP[first][end-first]) {
					minCut[end] = Math.min(minCut[end], 1 + minCut[first-1]);
				}
			}
		}
		
		return minCut[N-1];
	}
	
	public int minCut2(String s) {
		int N = s.length();
		boolean[][] isP = new boolean[N][N];
		int[] dp = new int[N+1];
		
		for (int i=0; i<=N; i++) dp[i] = i;
		
		for (int j=0; j<N; j++) {
			for (int i=0; i<=j; i++) {
				if (s.charAt(i) == s.charAt(j) && 
					(j-i<2 || isP[i+1][j-1])) {
					isP[i][j] = true;
					dp[j+1] = Math.min(dp[j+1], 1 + dp[i]);
				}
			}
		}
		
		return dp[N]-1;
	}
	
	@Test
	public void test1() {
		runTest(1, "aab");
	}
	
	@Test
	public void test2() {
		runTest(1, "abb");
	}
	
	@Test
	public void test3() {
		runTest(2, "abc");
	}
	
	@Test(groups="debug")
	public void test4() {
		runTest(1, "abazyxxyz");
	}
	
	private void runTest(int expected, String s) {
		assertEquals(new PalindromePartition2().minCut2(s), expected);
	}
}
